//1.无预处理记录
class Solution {
public:
    vector<vector<string>>  result;
    vector<string>  path;
    bool isPalindrome(const string& s, int start, int end) {
        while(start < end) {
            if(s[start] != s[end])
                return false;
            start++;
            end--;       
        }
        return true;
    }

    void act(const string& s, int startIndex) {
        if(startIndex >= s.size()){
            result.push_back(path);
            return;
        }
        for(int i=startIndex; i<s.size();++i) {
            if(isPalindrome(s, startIndex, i)) {
                string temp  = s.substr(startIndex, i-startIndex+1);
                path.push_back(temp);
            }
            else
                continue;

            act(s, i+1);
            path.pop_back();
        
        }   
    }

    vector<vector<string>> partition(string s) {
        act(s, 0);
        return result;
    }
};

//2.预处理记录一下回文串的数组，减少重复判断
class Solution {
public:
    vector<vector<string>>  result;
    vector<string>  path;
    vector<vector<int>> cunchu;
   

    void act(const string& s, int startIndex) {
        if(startIndex >= s.size()){
            result.push_back(path);
            return;
        }
        for(int i=startIndex; i<s.size();++i) {
            if(cunchu[startIndex][i]) {
                string temp  = s.substr(startIndex, i-startIndex+1);
                path.push_back(temp);
            }
            else
                continue;

            act(s, i+1);
            path.pop_back();
        
        }   
    }

    vector<vector<string>> partition(string s) {
        int n = s.size();
        cunchu.assign(n, vector<int>(n, 1));
        for(int i=n-2;i>=0;--i) {
            for(int j=i+1;j<n;++j) {
                cunchu[i][j] = (s[i]==s[j]) && cunchu[i+1][j-1];
            }
        }
        act(s, 0);
        return result;
    }
};